/*
https://leetcode-cn.com/problems/longest-valid-parentheses/solution/zui-chang-you-xiao-gua-hao-by-leetcode-solution/
 */
import java.util.Arrays;

public class Solution32 {
    public int longestValidParentheses(String s) {
        if (s.length()==0){
            return 0;
        }
        int[] f=new int[s.length()];
        for (int i=1;i<s.length();i++){
            if (s.charAt(i)==')'){
                if (s.charAt(i-1)=='('){
                    f[i]=(i>=2?f[i-2]:0)+2;
                }else if (i-f[i-1]>0 && s.charAt(i-f[i-1]-1)=='('){
                    f[i]=f[i-1]+(i-f[i-1]-2>=0?f[i-f[i-1]-2]:0)+2;
                }
            }
        }
        return Arrays.stream(f).max().getAsInt();
    }

    public static void main(String[] args) {
        System.out.println(new Solution32().longestValidParentheses("(()"));
    }
}
